package 牛客_面试必刷.Month07.day13;

import java.util.ArrayList;
import java.util.Arrays;

public class 有重复项数字的全排列 {
    ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        boolean[] arr = new boolean[num.length];
        Arrays.fill(arr,false);
        Arrays.sort(num);
        backstacking(num,arr);
        return lists;
    }

    public void backstacking(int[] nums,boolean[] arr){
        if(list.size() == nums.length){
            lists.add(new ArrayList<>(list));
        }

        for (int i = 0; i < nums.length; i++) {
            if(i > 0 && nums[i] == nums[i - 1] && arr[i - 1] == false) continue;
            if(arr[i] == false){
                list.add(nums[i]);
                arr[i] = true;
                backstacking(nums,arr);
                arr[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}
